\documentclass[submission]{FPSAC2017}

\articlenumber{32}
\addbibresource{32_Hetyei_Readdy_Ehrenborg.bib}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}

\numberwithin{equation}{section}

\newcommand{\SSSS}{{\mathfrak S}}

\newcommand{\Ppp}{{\mathbb P}}
\newcommand{\Rrr}{{\mathbb R}}
\newcommand{\Zzz}{{\mathbb Z}}
\newcommand{\vanish}[1]{}

\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\DP}{DP}
\DeclareMathOperator{\SP}{SP}
\DeclareMathOperator{\Head}{Head}
\DeclareMathOperator{\Tail}{Tail}
\DeclareMathOperator{\tw}{tw}

\usepackage{amssymb,amsmath,color}
\usepackage{tikz-dependency}
\usepackage{tikz}
\usepackage{enumerate}


\title[Type $B$ associahedron]{Realizing Simion's type $B$
  associahedron as a pulling triangulation of the Legendre polytope}

\author[Ehrenborg, Hetyei and Readdy]{Richard
  Ehrenborg\thanks{\href{mailto:richard.ehrenborg@uky.edu}{richard.ehrenborg@uky.edu}}\addressmark{1},
G\'abor Hetyei\thanks{\href{mailto:ghetyei@uncc.edu}{ghetyei@uncc.edu}}\addressmark{2} \and Margaret
  Readdy\thanks{\href{mailto:margaret.readdy@uky.edu}{margaret.readdy@uky.edu}}\addressmark{1}}

\address{\addressmark{1}Department of Mathematics, University of
  Kentucky, Lexington, KY 40506-0027\\ \addressmark{2}Department of Mathematics and Statistics,
  UNC-Charlotte, Charlotte NC 28223-0001}

\received{\today}

\abstract{We show that Simion's type $B$ associahedron is combinatorially
equivalent to a pulling triangulation of a type $B$ root polytope
called the Legendre polytope. 
Furthermore, we show that every pulling triangulation of the
Legendre polytope yields a flag complex.
Our triangulation refines a decomposition
of the Legendre polytope given by Cho.  We extend  Cho's cyclic
group action to the triangulation in such a way that it corresponds to
rotating centrally symmetric triangulations of a regular $(2n+2)$-gon.
\vanish{Finally, we present a bijection between the faces
of the Simion's type~$B$ associahedron
and Delannoy paths.}}

\resume{Nous montrons que l'associa\`edre du type $B$ de Simion est
  combinatoriellement \`equivalent \`a une triangulation obtenue en
  tirant les sommets d'un polytope des racines du type $B$, appel\'e 
le polytope de Legendre. De plus, nous montrons que toute
triangulation obtenue en tirant les sommets de ce polytope est un
complex de drapeau. Notre triangulation raffine une d\'ecomposition du 
polytope de Legendre donn\'e par Cho.  Nous \'eteignons l'action du
groupe cyclique de Cho \`a la triangulation tel qu'elle correspond \`a
la rotation des triangulations centrallement sym\'etriques d'un $(2n+2)$-gone
r\'egulier.}

\keywords{root polytope, associahedron, type $B$}


\begin{document}

\maketitle



\section{Introduction}

Root polytopes arising as convex hulls of roots in a root system have
become the subject of intensive interest in recent
years~\cite{Ardila,Clark-Ehrenborg,
Gelfand-Graev-Postnikov,Hetyei-Legendre,Meszaros_I,Meszaros_II}.
Another important
area where geometry meets combinatorics is the study of noncrossing
partitions, associahedra and their generalizations. In this context
Simion~\cite{Simion} constructed a type $B$ associahedron whose facets
correspond to centrally symmetric triangulations of a regular $(2n+2)$-gon.
Burgiel and Reiner~\cite{Burgiel-Reiner}
described Simion's construction as
providing ``the first motivating example for an equivariant generalization
of fiber polytopes, that is, polytopal subdivisions which are
invariant under symmetry groups''.
It was recently observed by Cori and Hetyei~\cite{Cori-Hetyei} that the
face numbers in this type $B$ associahedron are the same as the face
numbers in any pulling triangulation of the boundary of a type~$B$ root
polytope, called the Legendre polytope in~\cite{Hetyei-Legendre}.

In this presentation we explain that the equality of these face numbers is not a
mere coincidence: the type~$B$ associahedron is combinatorially
equivalent to a pulling triangulation of the Legendre polytope $P_{n}$. The
convex hull of the positive roots among the vertices of the Legendre
polytope and of the origin is a type $A$ root polytope
$P_{n}^{+}$. Cho~\cite{Cho} has shown that the Legendre polytope $P_{n}$ may be
decomposed into copies of $P_{n}^{+}$ that meet only on their boundaries and
that there is a $\Zzz_{n+1}$-action on this decomposition. Our
triangulation representing the type~$B$ associahedron as a triangulation
of the Legendre polytope refines Cho's decomposition in such a way that
extends the $\Zzz_{n+1}$-action to the
triangulation. The effect of this $\Zzz_{n+1}$-action on the
centrally symmetric triangulations of the $(2n+2)$-gon is rotation.


\vanish{This extended abstract is structured as follows.
In the preliminaries we discuss the Simion type~$B$ associahedron,
the Legendre polytope and pulling triangulations.
In \cref{section_flag}
we show that every pulling triangulation of the Legendre polytope
is a flag complex. We introduce
an arc representation of Simion's type~$B$ diagonals in
\cref{section_arc} and obtain conditions for when a pair of
$B$-diagonals do not cross. A bijection
between the set of $B$-diagonals and the vertex set of the Legendre
polytope is obtained by the intermediary of our arc representation in
\cref{section_embed}. We characterize when $B$-diagonals cross in
terms of crossing and nesting conditions on the arrows associated to the
vertices of the Legendre polytope. This characterization is used in
\cref{section_triangulation} to define a triangulation of the boundary of
the Legendre polytope where each face corresponds to a face in the
type~$B$ associahedron. 
Since both complexes are flag and have
the same minimal non-faces,
we conclude that they are the same polytope.
We end this section by
describing the facets in our triangulation.
In \cref{section_Cho}
we prove that our triangulation refines Cho's
decomposition and that his $\Zzz_{n+1}$-action corresponds to
rotating the regular $(2n+2)$-gon.   

We conclude with comments and future research directions.}

\section{Preliminaries}
\label{section_preliminaries}

\subsection{Simion's type $B$ associahedron}

Simion~\cite{Simion} introduced a simplicial complex denoted by~$\Gamma_{n}^{B}$ 
on  $n(n+1)$ vertices as follows. Consider a centrally 
symmetric convex $(2n+2)$-gon, and label its vertices in the clockwise
order with $1$, $2$, \ldots, $n$, $n+1$, $\overline{1}$, $\overline{2}$,
\ldots, $\overline{n}$,  $\overline{n+1}$. The vertices 
of $\Gamma_{n}^{B}$ are the {\em $B$-diagonals}, which are one of the two
following kinds: diagonals joining antipodal pairs of points, and
antipodal pairs of noncrossing diagonals. The diagonals joining
antipodal points are all pairs of the form
$\{i,\overline{i}\}$ satisfying $1\leq i\leq n+1$, and they are called
{\em diameters}. The $B$-diagonals
that are antipodal pairs of noncrossing  diagonals are either of the form
$\{\{i,j\},\{\overline{i},\overline{j}\}\}$ satisfying $1\leq
i<i+1<j\leq n+1$ or of the form $\{\{i,\overline{j}\}, 
\{\overline{i},j\}\}$ satisfying $1\leq j< i\leq n+1$.

The simplicial complex  $\Gamma_{n}^{B}$ is the family of sets of pairwise
noncrossing $B$-diagonals. Simion showed the
simplicial complex $\Gamma_{n}^{B}$ is the boundary complex of an
$n$-dimensional convex polytope. 
The dual of this polytope
is also known as
the Bott--Taubes polytope~\cite{Bott_Taubes}
and
the cyclohedron~\cite{Markl}.
Associahedra are usually defined as simple
polytopes. However,
Simion followed Perles' convention by calling this simplicial
polytope the associahedron. Since the only associahedron we will consider is
the one constructed by Simion, we prefer to use her nomenclature.


Simion also computed the face
numbers and $h$-vector.
These turn
out to be identical with the face numbers and $h$-vector of any pulling
triangulation of the Legendre polytope.
We will discuss this polytope in the next subsection. We end with a fact
that is implicit in the work of  
Simion~\cite[Section~3.3]{Simion}.
\begin{lemma}[Simion]
\label{lemma_diameter}
Each facet $\Gamma_{n}^{B}$
of Simion's type~$B$ associahedron
contains exactly one $B$-diagonal of the form
$\{i,\overline{i}\}$ connecting an antipodal pair of points.  
\end{lemma}


\subsection{The Legendre polytope or ``full'' type $A$ root polytope} 

Consider an $(n+1)$-dimensional Euclidean space
with orthonormal basis $\{e_1, \ldots, e_{n+1}\}$.
The convex hull of the vertices
$\pm 2e_1$, \ldots, $\pm 2 e_{n+1}$
is an $(n+1)$-dimensional cross-polytope.
The intersection of this cross-polytope with the hyperplane
$x_{1} + x_{2} + \cdots + x_{n+1} = 0$
is an $n$-dimensional centrally
symmetric polytope $P_{n}$ first studied by Cho~\cite{Cho}.
It is called
the {\em Legendre polytope}
in the work of Hetyei~\cite{Hetyei-Legendre},
since the polynomial
$\sum_{j=0}^{n} f_{j-1} \cdot ((x-1)/2)^{j}$
is the $n$th Legendre polynomial, where $f_{i}$ is the number of
$i$-dimensional faces in any pulling triangulation of the boundary of $P_{n}$.
See \cref{lemma_any_pull} below.
Furthermore, it is called
the ``full'' type $A$ root polytope in the work of
Ardila--Beck--Ho\c{s}ten--Pfeifle--Seashore~\cite{Ardila}. It has
$n(n+1)$ vertices consisting of all points of the 
form $e_{i}-e_{j}$ where $i\neq j$. 

We use the shorthand notation $(i,j)$
for the vertex $e_{j}-e_{i}$ of the Legendre polytope $P_{n}$.
We may think of these vertices as the set of all
directed nonloop edges on the vertex set $\{1,2,\ldots,n+1\}$.
A subset of
these edges is contained in some face of $P_{n}$
exactly when there is no
$i \in \{1,2,\ldots,n+1\}$ that is both the head and the tail of a
directed edge.
Equivalently, the faces are described as follows.
\begin{lemma}
The faces of the Legendre polytope $P_{n}$
are of the form
$\conv(I \times J) = \conv(\{(i,j) \: : \: i \in I, j \in J\})$
where 
$I$ and $J$ are two non-empty disjoint subsets
of the set $\{1,2,\ldots,n+1\}$.
The dimension of a face is given by
$|I| + |J| - 2$.
A face is a facet if and only if the union of $I$ and $J$ is
the set $\{1,2,\ldots,n+1\}$.
\label{lemma_facets}
\end{lemma}
\noindent
Especially, when the two sets $I$ and $J$
both have cardinality two, the associated 
face is \vanish{geometrically} a square.
Furthermore, the other two-dimensional faces
are equilateral triangles.


Affine independent subsets of vertices of faces of the Legendre
polytope are
easy to describe. A set $S=\{(i_1,j_1),(i_2,j_2),\ldots, (i_{k},j_{k})\}$ is a
$(k-1)$-dimensional simplex if and only if, 
disregarding the orientation of the directed
edges, the set $S$ contains no
cycle, that is, it is a forest~\cite[Lemma~2.4]{Hetyei-Legendre}. 

The Legendre polytope $P_{n}$ contains the polytope $P_{n}^{+}$, defined as the convex
hull of the origin and the set of points $e_{i}-e_{j}$, where $i<j$. The
polytope $P_{n}^{+}$ was first studied by Gelfand, Graev and
Postnikov~\cite{Gelfand-Graev-Postnikov} and later by
Postnikov~\cite{Postnikov-P}.
Some of the results on $P_{n}^{+}$ may be easily
generalized to~$P_{n}$.


\subsection{Pulling triangulations}


The notion of pulling triangulations is 
originally due to Hudson~\cite[Lemma~1.4]{Hudson}.
For more modern formulations, see~\cite[Lemma~1.1]{Stanley-Dec}
and~\cite[End of Section~2]{Athanasiadis}.
We refer to~\cite[Section~2.3]{Hetyei-Legendre} for the version
presented here.

For a polytopal complex ${\mathcal P}$ 
and a vertex $v$ of ${\mathcal P}$,
let ${\mathcal P}- v$ be the complex consisting
of all faces of~${\mathcal P}$ not
containing the vertex $v$.
Also for a facet $F$ let
${\mathcal P}(F)$ be the complex of all
faces of ${\mathcal P}$ contained in~$F$.

\begin{definition}[Hudson]
\label{definition_pull}
Let  ${\mathcal P}$  be a polytopal complex and let $<$ be a linear
order on the set~$V$ of its vertices. The pulling triangulation
$\triangle({\mathcal P})$ with respect to $<$ is defined
recursively as follows. We set 
$\triangle({\mathcal P})={\mathcal P}$ if ${\mathcal P}$ consists
of a single vertex. Otherwise let $v$ be the least element of $V$ with
respect to $<$ and set 
$$
\triangle({\mathcal P})
=
\triangle({\mathcal P}- v)\cup
\bigcup_F \left\{ \conv(\{v\}\cup G)\::\: G\in
\triangle({\mathcal P}(F))\right\} ,
$$
where the union runs over the facets $F$ not containing $v$ of the
maximal faces of ${\mathcal P}$ which contain~$v$.
The triangulations
$\triangle({\mathcal P}- v)$ and $\triangle({\mathcal P}(F))$ are
with respect to the order~$<$
restricted to their respective vertex sets.
\end{definition}

\begin{theorem}[Hudson]
The pulling triangulation $\triangle({\mathcal P})$
is a triangulation of
the polytopal complex~${\mathcal P}$
without introducing any new vertices.
\label{theorem_pull}
\end{theorem}



In particular, any pulling triangulation of the
boundary of $P_{n}$  is compressed as defined by
Stanley~\cite{Stanley-Dec}, and has the same face 
numbers~\cite[Corollary 4.11]{Hetyei-Legendre}. This important fact
and the analogous statement for $P_{n}^{+}$ is a direct consequence of the
following two fundamental results~\cite{Heller,Heller-Hoffman,Stanley-Dec}.
\begin{proposition}[Stanley]
\label{proposition_compress}
Suppose that one of the vertices of a polytope $P$ is the origin and that the
matrix whose rows are the coordinates of   
the vertices of $P$ is totally unimodular.
Let $<$ be any ordering on the vertex set of~$P$ such that the
origin is the least vertex with respect to $<$. Then the pulling order
$<$ is compressed, that is, all of the facets in the induced triangulation
have the same relative volume.
\end{proposition} 
\begin{theorem}[Heller]
\label{theorem_Heller}
The incidence matrix of a directed graph is totally unimodular.
\end{theorem}

\subsection{Face vectors of pulling triangulations of
the Legendre polytope}

Among all triangulations of the boundary of the Legendre polytope $P_{n}$
obtained by pulling
the vertices, counting faces is most easily performed for the
{\em lexicographic triangulation}
in which we pull $(i,j)$ before $(i',j')$ exactly when
$i<i'$ or when $i=i'$ and $j<j'$. Counting faces in this
triangulation amounts to counting lattice paths;
see~\cite[Lemma~5.1]{Hetyei-Legendre}
and~\cite[Proposition~17]{Ardila}. From this we
obtain the following expression for the face 
numbers~\cite[Theorem~5.2]{Hetyei-Legendre}. 
\begin{lemma}[Hetyei]
For any pulling triangulation of the boundary of $P_{n}$,
the number $f_{j-1}$ of $(j-1)$-dimensional faces is 
\begin{equation}
\label{equation_f}
f_{j-1}=\binom{n+j}{j}\binom{n}{j} \quad \mbox{for $0\leq j\leq n$}.
\end{equation}    
\label{lemma_any_pull}  
\end{lemma}
\vanish{It was first noted in~\cite{Cori-Hetyei} that
these face numbers are the
same as that of Simion's type $B$ associahedron~$\Gamma_{n}^{B}$.
\cref{theorem_r_pull} will explicitly explain this fact 
by showing that
$\Gamma_{n}^{B}$ can be realized
as a pulling triangulation of the Legendre polytope.}




\section{The flag property}
\label{section_flag}


Recall that a simplicial complex is a {\em flag complex} if every
minimal nonface has two elements.
The main result of this section is the following.
\begin{theorem}
\label{theorem_pull_flag}  
Every pulling triangulation of the boundary of the Legendre polytope
$P_{n}$ is a flag simplicial complex.
\end{theorem}

A key ingredient for proving this theorem and
\cref{theorem_r_pull} is the following observation. 
\begin{lemma}
Let $\{x_{1},x_{2},y_{1},y_{2}\}$ be a four element subset of the set
$\{1,2, \ldots, n+1\}$. Then the set
$\{x_{1},x_{2}\} \times \{y_{1},y_{2}\} = 
\{(x_{1},y_{1}),(x_{1},y_{2}),(x_{2},y_{2}),(x_{2},y_{1})\}$
is the vertex set of a square face of the Legendre polytope $P_{n}$, and the sets
$\{(x_{1},y_{1}), (x_{2},y_{2})\}$ and $\{(x_{1},y_{2}), (x_{2},y_{1})\}$
are the diagonals of this square. For any pulling triangulation the
diagonal containing the vertex that was pulled first is an edge of the
triangulation and the other diagonal is not an edge.
\label{lemma_square}
\end{lemma}

Since the Cartesian product of an $m$-dimensional simplex
and an $n$-dimensional simplex is a face of
the Legendre polytope of dimension $m+n+1$, we obtain the following
corollary. 
\begin{corollary}
Every pulling triangulation of the Cartesian product of
two simplices is a flag complex.
\end{corollary}




\section{The arc representation of $\Gamma_{n}^{B}$}
\label{section_arc}

\begin{figure}
\centering
\begin{tikzpicture}
%% First draw the first circle
\draw(0mm,0mm) circle (20mm);

%% The 16 marks, each 2mm long
\draw(0mm,20mm) -- (0mm,22mm);
\draw(7.653mm,18.477mm) -- (8.419mm,20.325mm);
\draw(14.142mm,14.142mm) -- (15.556mm,15.556mm);
\draw(18.477mm,7.653mm) -- (20.325mm,8.419mm);
\draw(20mm,0mm) -- (22mm,0mm);
\draw(18.477mm,-7.653mm) -- (20.325mm,-8.419mm);
\draw(14.142mm,-14.142mm) -- (15.556mm,-15.556mm);
\draw(7.653mm,-18.477mm) -- (8.419mm,-20.325mm);
\draw(0mm,-20mm) -- (0mm,-22mm);
\draw(-7.653mm,-18.477mm) -- (-8.419mm,-20.325mm);
\draw(-14.142mm,-14.142mm) -- (-15.556mm,-15.556mm);
\draw(-18.477mm,-7.653mm) -- (-20.325mm,-8.419mm);
\draw(-20mm,0mm) -- (-22mm,0mm);
\draw(-18.477mm,7.653mm) -- (-20.325mm,8.419mm);
\draw(-14.142mm,14.142mm) -- (-15.556mm,15.556mm);
\draw(-7.653mm,18.477mm) -- (-8.419mm,20.325mm);

%% Put in the labels 1 through \overline{8}
\label(0mm,0mm)
[label distance=100mm] 
\node[circle,
label=90:$1$,
label=70:$2$,
label=45:$3$,
label=20:$4$,
label=0:$5$, 
label=340:$6$, 
label=315:$7$, 
label=290:$8$, 
label=270:$\overline{1}$, 
label=250:$\overline{2}$, 
label=225:$\overline{3}$, 
label=200:$\overline{4}$, 
label=180:$\overline{5}$, 
label=160:$\overline{6}$,
label=135:$\overline{7}$,
label=110:$\overline{8}$
]{\hspace*{40mm}}; 

%% The B-diagonal
\draw[line width=0.3mm](7.653mm,18.477mm) -- (20mm,0mm);
\draw[line width=0.3mm](-7.653mm,-18.477mm) -- (-20mm,0mm);

%% The two arcs
\draw[line width=0.3mm] (27.716mm,11.480mm)
arc (22.5:67.5:30mm);
\draw[line width=0.3mm] (-27.716mm,-11.480mm)
arc (202.5:247.5:30mm);

\end{tikzpicture}
\hspace*{10mm}
\raisebox{0mm}{
\begin{tikzpicture}

%% First draw the second circle
\draw(0mm,0mm) circle (10mm);

%% The 8 marks, each 2mm long
\draw(0mm,10mm) -- (0mm,12mm);
\draw(7.071mm,7.071mm) -- (8.485mm,8.485mm);
\draw(10mm,0mm) -- (12mm,0mm);
\draw(7.071mm,-7.071mm) -- (8.485mm,-8.485mm);
\draw(0mm,-10mm) -- (0mm,-12mm);
\draw(-7.071mm,-7.071mm) -- (-8.485mm,-8.485mm);
\draw(-10mm,0mm) -- (-12mm,0mm);
\draw(-7.071mm,7.071mm) -- (-8.485mm,8.485mm);

%% Put in the labels 1 through 8
\label(0mm,0mm)
[label distance=100mm] 
\node[circle,
label=90:$1$,
label=45:$2$,
label=0:$3$, 
label=315:$4$, 
label=270:$5$, 
label=225:$6$, 
label=180:$7$, 
label=135:$8$,
]{\hspace*{20mm}}; 

%% The one arc
\draw[line width=0.3mm] (14.142mm,-14.142mm)
arc (315:405:20mm);

%% The one arrow
\draw[line width=0.3mm] (17.677mm,-17.677mm)
arc (315:45:25mm);

%% The arrow head
\draw[line width=0.3mm] (15.677mm,17.677mm)
-- (17.677mm,17.677mm) -- (17.677mm,19.677mm);

\end{tikzpicture}
}
\caption{The arc representation of the $B$-diagonal
consisting of the two diagonals $\{2,5\}$ and
$\{\overline{2},\overline{5}\} = \{10,13\}$
is the two arcs $[2,4]$ and $[\overline{2},\overline{4}] = [10,12]$.
By considering the arcs modulo $n+1=8$
(see the second circle)
we obtain that this $B$-diagonal is represented by the arrow~$(4,2)$.}
\label{figure_one}
\end{figure}



\vanish{In this section we describe a representation of $\Gamma_{n}^{B}$ as a
simplicial complex whose vertices
are centrally symmetric pairs of ``arcs''
on a circle. This representation has a natural circular symmetry.}


Consider a regular $(2n+2)$-gon whose vertices are labeled $1,2,
\ldots,n+1,\overline{1},\overline{2}, \ldots,
\overline{n+1}$ in the clockwise order. Identify each vertex 
$\overline{i}$ with $n+1+i$ for $i=1,2,\ldots, n+1$. Subject to this
identification, each $B$-diagonal, may be represented as an unordered
pair of diagonals of the form $\{\{u,v\},\{u+n+1,v+n+1\}\}$ for some
$2$-element subset 
$\{u,v\}$ of $\{1,2,\ldots, 2n+2\}$, where addition is
modulo~$2n+2$. For $B$-diagonals $\{k, \overline{k}\}$ joining antipodal
points, the unordered pair $\{\{k,k+n+1\}, \{k+n+1,k+2n+2\}\}$ contains
two copies of the same two-element set.  


For any two points $x$ and $y$ on the circle $\Rrr/(2n+2)\Zzz$ 
which are not antipodal, let
$[x,y]$ denote the shortest arc from $x$ to $y$.


\begin{definition}
\label{definition_arc-representation}
We define the {\em arc-representation} on the vertices of
$\Gamma_{n}^{B}$ as
follows. Subject to the above identifications, represent the 
$B$-diagonal $\{\{u,v\}, \{u+n+1, v+n+1\}\}$ with the centrally
symmetric pair of arcs $\{[u,v-1], [u+n+1,v+n]\}$ on the 
circle $\Rrr/(2n+2)\Zzz$.
\end{definition}
\vanish{The representation above is well-defined: for any pair of
vertices $u$ and $v$,
the arc $[u,v-1]$ and the arc $[u+n+1,v+n]$ form a centrally symmetric
pair, so the definition is independent of the selection of the element
of $\{\{u,v\}, \{u+n+1,v+n+1\}\}$.} Note that for $B$-diagonals of
the form $\{\{k,n+1+k\},\{k,n+1+k\}\}$ corresponding to antipodal pairs
of points, the union of the arcs $[k,k+n]$ and $[k+n+1,k-1]$ is not
the full circle.
 
See \cref{figure_one} for an example where
$n=7$ with the $B$-diagonal $\{\{2,5\},\{\overline{2},\overline{5}\}\}$.
 
\begin{lemma}
The arc-representation of the vertices of $\Gamma_{n}^{B}$ is one-to-one:
distinct $B$-diagonals are mapped to distinct centrally symmetric pairs 
of arcs.
\end{lemma}  
\vanish{Indeed, the pair $\{[u,v-1],[u+n+1,v+n]\}$ can only be the image of the
unordered pair $\{\{u,v\},\{u+n+1,v+n+1\}\}$.} 

The following theorem plays an important role in 
connecting the type $B$ associahedron with the Legendre polytope.
\begin{theorem}
\label{theorem_across}
The $B$-diagonal represented by the pair of arcs 
$\{[u_{1}, v_{1}-1], [u_{1}+n+1,v_{1}+n]\}$ and the $B$-diagonal
represented by the pair of arcs $\{[u_{2}, v_{2}-1], [u_{2}+n+1,v_{2}+n]\}$ are
noncrossing if and only if for either arc $I\in \{[u_{1},
  v_{1}-1],[u_{1}+n+1,v_{1}+n]\}$ and for either arc $J\in \{[u_{2}, v_{2}-1],
[u_{2}+n+1,v_{2}+n]\}$, the arcs $I$ and $J$ are either nested or disjoint.  
\end{theorem}
\vanish{
\begin{proof}
Assume first that the two $B$-diagonals cross. Since we may replace
$\{u_{i},v_{i}\}$ with $\{u_{i}+n+1,v_{i}+n+1\}$ if necessary, without loss of
generality we may assume that the diagonal $\{u_{1},v_{1}\}$ crosses the
diagonal $\{u_{2},v_{2}\}$.
Exactly one of the
endpoints of the diagonal $\{u_{2},v_{2}\}$ must then belong to the arc
$[u_{1}+1,v_{1}-1]$ and the other one does not belong even to the larger arc
$[u_{1},v_{1}]$. If $u_{2}\in [u_{1}+1,v_{1}-1]$ and $v_{2}\not\in [u_{1},v_{1}]$ 
then we have
$$
[u_{1}, v_{1}-1]\cap [u_{2}, v_{2}-1]=[u_{2},v_{1}-1].
$$
This arc contains $u_{2}$, but does not contain $u_{1}$ (since $u_{2}\in
[u_{1}+1,v_{1}-1]$), nor does it contain $v_{2}-1\not \in [u_{1},v_{1}-1]$. The
arcs $[u_{1}, v_{1}-1]$  and $[u_{2}, v_{2}-1]$ do not contain each other
and they are not disjoint.

If $v_{2}\in [u_{1}+1,v_{1}-1]$ and $u_{2}\not\in [u_{1},v_{1}]$ 
then we have
$$
[u_{1}, v_{1}-1]\cap [u_{2}, v_{2}-1]=[u_{1},v_{2}-1].
$$
Similar to the previous case, we obtain that the arcs $[u_{1}, v_{1}-1]$
and $[u_{2}, v_{2}-1]$ do not contain each other and they are not disjoint.

Assume next that the two diagonals do not cross. If $u_{2}\in
[u_{1}+1,v_{1}-1]$ then we must have $v_{2}\in [u_{2}+1,v_{1}]$, implying 
$$
[u_{1}, v_{1}-1]\cap [u_{2}, v_{2}-1]=[u_{2},v_{2}-1].
$$
Similarly, if $v_{2}\in [u_{1}+1,v_{1}-1]$ then we must have $u_{2}\in
[u_{1},v_{2}]$, implying
$$
[u_{1}, v_{1}-1]\cap [u_{2}, v_{2}-1]=[u_{2},v_{2}-1].
$$
Finally, if neither $u_{2}$ nor $v_{2}$ belongs to $[u_{1}+1,v_{1}-1]$ then
either the arc $[u_{2},v_{2}-1]$ contains the arc $[u_{1},v_{1}-1]$ or it is disjoint from it. 
The above argument remains valid if we replace either (or both) of
$[u_{1}, v_{1}-1]$ and $[u_{2}, v_{2}-1]$ with the arc $[u_{1}+n+1, v_{1}+n]$ or
$[u_{2}+n+1, v_{2}+n]$, respectively. 
\end{proof}}
\begin{corollary}
\label{corollary_across}  
The $B$-diagonal represented by the pair of arcs 
$\{[u_{1}, v_{1}-1], [u_{1}+n+1,v_{1}+n]\}$ and the $B$-diagonal
represented by the pair of arcs $\{[u_{2}, v_{2}-1], [u_{2}+n+1,v_{2}+n]\}$ are
noncrossing if and only the set $[u_{1}, v_{1}-1]\cup [u_{1}+n+1,v_{1}+n]$ and
the set $[u_{2}, v_{2}-1]\cup [u_{2}+n+1,v_{2}+n]$ are nested or disjoint. 
\end{corollary}  



\section{Embedding $\Gamma_{n}^{B}$ as a family of simplices on $\partial P_{n}$}
\label{section_embed}

\vanish{In this section we describe a way to represent the boundary complex
$\Gamma_{n}^{B}$ of Simion's type $B$ associahedron as a family
of simplices on the vertex set of the Legendre polytope $P_{n}$. We do
this so that each simplex is contained in a face of the
boundary $\partial P_{n}$ of $P_{n}$. In \cref{section_triangulation} we will
prove that our map represents the boundary complex of the type $B$
associahedron as a pulling triangulation of $\partial P_{n}$.} 
 
We begin by defining a bijection between the vertex set of $\Gamma_{n}^{B}$
and that of $P_{n}$.
Recall that we use
the shorthand notation $(i,j)$ for the vertex $e_{j}-e_{i}$ of $P_{n}$.
We refer to $(i,j)$ as {\em the arrow  from $i$ to $j$}. Using the term
``arrow'' as opposed to ``directed edge'' will eliminate the
confusion that $e_{j}-e_{i}$ is a vertex of $P_{n}$.
\vanish{Instead we think of it as an arrow from $i$ to $j$ in the complete
directed graph on the vertex set $\{1,2,\ldots,n+1\}$ having no loops.}

\begin{definition}
\label{definition_arrow_representation}
Let $\{[i,j], [\overline{i},\overline{j}]\}$ be the arc representation
of a $B$-diagonal in $\Gamma_{n}^{B}$,
where $1 \leq i \leq n+1$ and $i < j$.
Define {\em the arrow representation} 
of this $B$-diagonal in $P_{n}$ to be the arrow~$(j,i)$.
\end{definition}
In other words,
the arrow encodes the complement of
the image of the arcs in the circle $\Rrr/(n+1)\Zzz$.
We refer to
the second circle in \cref{figure_one}
for the continuation of the example 
of the $B$-diagonal $\{\{2,5\},\{\overline{2},\overline{5}\}\}$.

\vanish{When making this definition explicit for
a $B$-diagonal $\{\{i,j\},\{\overline{i}, \overline{j}\}\}$,
we obtain several cases:
\begin{enumerate}[(1)]
\item
For each $i$ satisfying $2 \leq i \leq n+1$,
represent the $B$-diagonal
$\{i,\overline{i}\}$ connecting two antipodal points with
the arrow~$(i-1,i)$. Represent the $B$-diagonal $\{1,\overline{1}\}$
with the arrow~$(n+1,1)$.
\item
For each $i$ and $j$ satisfying $1\leq i<i+1<j\leq n+1$,  
represent the $B$-diagonal $\{\{i,j\},\{\overline{i}, \overline{j}\}\}$
with the arrow~$(j-1,i)$.
\item
For each $i$ and $j$ satisfying $2\leq j<i\leq n+1$, 
represent the $B$-diagonal
$\{\{i,\overline{j}\}, \{\overline{i},j\}\}$
with the arrow~$(j-1,i)$. For each $i$ satisfying $2 \leq i \leq n+1$,
represent the $B$-diagonal $\{\{1,\overline{i}\},\{\overline{1},i\}\}$
with the arrow~$(n+1,i)$.
\end{enumerate}

This representation yields a bijection between 
$B$-diagonals and arrows. The inverse map is given as follows:
\begin{enumerate}[(a)]
\item
For $i$ satisfying $1 \leq i \leq n$,
the arrow $(i,i+1)$ represents the $B$-diagonal $\{i+1,\overline{i+1}\}$
and
the arrow $(n+1,1)$ represents the $B$-diagonal $\{1,\overline{1}\}$.
\item
For each $i$ and $j$ satisfying $1\leq i<j\leq n$, the arrow
$(j,i)$ represents the $B$-diagonal
$\{\{i,j+1\},\{\overline{i},\overline{j+1}\}\}$. 
\item
For each $i$ and $j$ satisfying $1\leq j<i-1<i\leq n+1$, the
arrow $(j,i)$ represents the $B$-diagonal
$\{\{i,\overline{j+1}\},\{\overline{i},j+1\}\}$, and for  
$2 \leq i \leq n+1$, the arrow $(n+1,i)$
represents the $B$-diagonal $\{\{1,\overline{i}\}, \{\overline{1},i\}\}$.   
\end{enumerate} 






The $B$-diagonals in
item~(1) of
\cref{definition_arrow_representation}
may be thought of as a ``degenerate case'' of the $B$-diagonals
in item~(3). In the case when $i=j$, the set
$\{\{\overline{i},j\},\{i,\overline{j}\}\}$ becomes a singleton, and the
rules in item~(1) may be obtained by extending the rules
in item~(3) in an obvious way. On the other hand,
\cref{definition_arrow_representation} has a simpler form in
terms of the arc-representation 
described in \cref{section_arc} and in terms of the following
continuous map.}

\begin{definition}
\label{definition_pi}
Define the map
$\pi: \Rrr/(2n+2)\Zzz \longrightarrow \Rrr/(n+1)\Zzz$
to be the modulo $n+1$ map.
Furthermore, identify the circle $\Rrr/(n+1)\Zzz$
with the half-open interval
$(0,n+1]$.
Thus the map $\pi$ sends each $x \in (0,n+1]$ to~$x$
and each $x \in (n+1,2n+2]$ to $x-n-1$.  
\end{definition}
Although the map $\pi$ depends on $n$,
we suppress this dependency in our notation.
Also observe that the map $\pi$ is a two-to-one mapping:
for each $y\in \Rrr/(n+1)\Zzz$ we have $|\pi^{-1}(y)|=2$.




\begin{remark}
\label{remark_arrows}
{\em  For any pair of arcs $\{[u,v-1],[u+n+1,v+n]\}$ there is a unique way to
select~$u$ to be an element of the set $\{1,2,\ldots,n+1\}$,
that is, $\pi(u)=u$. We may distinguish two
cases depending upon whether the arc $[u,v-1]$ is a subset of the arc
$[u,n+1]$ or not.
\begin{enumerate}[(i)]
\item
If $[u,v-1]\subseteq [u,n+1]$ then visualize
the set $\pi([u,v-1])=\pi([u+n+1,v+n])$ as the subinterval
$[u,v-1]$ of $(0,n+1]$. The direction of both arcs
$[u,v-1]$ and $[u+n+1,v+n]$ corresponds to parsing the interval
$[u,v-1]$ in increasing order. Adding the associated backward arrow
$(v-1,u)$ closes a directed cycle with this directed interval.
$$
\begin{tikzpicture}
\draw (0,0) -- (8,0);
\foreach \x in {0,...,8}
\draw (\x,-0.2) -- (\x,0.2);
\foreach \x in {0,...,8}
\node[black] at (\x,-0.4) {\small$\x$};

\node[anchor=east] at (4.3,0) (text) {};
\node[anchor=west] at (1.7,0) (description) {};
\draw[line width=0.5mm] (description) edge[out=0,in=180,->] (text);

\node[anchor=east] at (2,0.2) (text) {};
\node[anchor=west] at (4,0.2) (description) {};
\draw[line width=0.5mm] (description) edge[out=135,in=45,->] (text);
\end{tikzpicture}
$$
As an example, when $n=7$ then the $B$-diagonal 
$\{\{2,5\},\{\overline{2},\overline{5}\}\}$
is represented by the backward arrow $(4,2)$
as drawn above on the interval $(0,8]$.
\item
If the
arc $[u,v-1]$ is not contained in the arc 
$[u,n+1]$ then $n+1 < v-1 < u+n+1$.
The integer $\pi(v-1)=v-1-(n+1)$ is congruent to $v-1$ modulo~$(n+1)$
and satisfies $1\leq \pi(v-1)<u$.
The image of the arc $[u,v-1]$ under $\pi$,
that is,
$\pi([u,v-1])=\pi([u+n+1,v+n])$ is then the subset 
$(0,\pi(v)-1]\cup [u,n+1]$ of the interval $(0,n+1]$.
We may consider $(0,\pi(v)-1]\cup [u,n+1]$ as a ``wraparound
interval'' modulo~$n+1$ from $u$ to $\pi(v-1)$.
The direction of both pieces
corresponds to listing the elements of this ``wraparound
interval'' in increasing order modulo $n+1$.  
Adding the associated forward arrow $(\pi(v-1),u)$ closes a directed
cycle with the directed wraparound interval.
$$
\begin{tikzpicture}
\draw (0,0) -- (8,0);
\foreach \x in {0,...,8}
\draw (\x,-0.2) -- (\x,0.2);
\foreach \x in {0,...,8}
\node[black] at (\x,-0.4) {\small$\x$};

\node[anchor=east] at (3.3,0) (text) {};
\node[anchor=west] at (-0.3,0) (description) {};
\draw[line width=0.5mm] (description) edge[out=0,in=180,->] (text);

\node[anchor=east] at (8.3,0) (text) {};
\node[anchor=west] at (5.7,0) (description) {};
\draw[line width=0.5mm] (description) edge[out=0,in=180,->] (text);

\node[anchor=east] at (6.2,0.2) (text) {};
\node[anchor=west] at (2.8,0.2) (description) {};
\draw[line width=0.5mm] (description) edge[out=45,in=135,->] (text);
\end{tikzpicture}
$$
For instance, when $n = 7$
the $B$-diagonal $\{\{4,\overline{6}\},\{\overline{4},6\}\}$
yields the forward arrow $(3,6)$.
\end{enumerate}
}
\end{remark}

\begin{proposition}
\label{proposition_crossing_pi}
The $B$-diagonal represented by the arrow $(\pi(v_{1}-1),\pi(u_{1}))$ and
the $B$-diagonal represented by the arrow $(\pi(v_{2}-1),\pi(u_{2}))$
are noncrossing if and only if the images $\pi([u_{1},v_{1}-1])$ and
$\pi([u_{2},v_{2}-1])$ are disjoint or contain each other.  
\end{proposition}
\vanish{\begin{proof}
The statement is an easy consequence of the following observation.
Both arcs of the arc representation $\{[u,v-1],[u+n+1,v+n]\}$ of a
$B$-diagonal are mapped onto the same arc $[\pi(u),\pi(v-1)]$ by
$\pi$ and $[u,v-1]\cup [u+n+1,v+n]=\pi^{-1}([\pi(u),\pi(v-1)])$. 
\end{proof}}


\vanish{
Next we translate the noncrossing conditions for $B$-diagonals into
conditions for the arrows representing them.}
\begin{proposition}
\label{proposition_across}
Suppose a pair of $B$-diagonals is represented by a pair of arrows as
defined in \cref{definition_arrow_representation}.
These $B$-diagonals cross
if and only if one of the following conditions is satisfied:
\begin{enumerate}[(1)]
\itemsep=-5pt  
\item Both arrows are backward and they cross.
\item Both arrows are forward and they do not nest.
\item One arrow is forward, the other one is backward, and
the backward arrow nests or crosses the forward arrow.
\item The head of one arrow is the tail of the other arrow.
\end{enumerate}    
\end{proposition}  
\vanish{\begin{proof}
Suppose the arc representations of the two $B$-diagonals are
$\{[u_{1},v_{1}-1],[u_{1}+n+1,v_{1}+n]\}$ and $\{[u_{2},v_{2}-1],[u_{2}+n+1,v_{2}+n]\}$,
respectively. By \cref{proposition_crossing_pi}, the represented $B$-diagonals
are crossing if and only if the images
$\pi([u_{1},v_{1}-1])$ and 
$\pi([u_{2},v_{2}-1])$
are not disjoint and do not contain each other.

We will consider three cases, depending on the
direction of the two arrows $(\pi(v_{1}-1),\pi(u_{1}))$ and
$(\pi(v_{2}-1),\pi(u_{2}))$. These arrows are either both forward, 
both backward or have opposite directions.

If both arrows are backward then neither the image
$\pi([u_{1},v_{1}-1])$ nor the image $\pi([u_{2},v_{2}-1])$
contain the point $n+1$.
Two such intervals intersect nontrivially in an interval of positive length
exactly when the corresponding arrows cross. They intersect in a
single point exactly when there is a vertex that is the tail of one of
the arrows and the head of the other arrow.

If both arrows are forward then both images
$\pi([u_{1},v_{1}-1])$ and $\pi([u_{2},v_{2}-1])$ contain
the point $n+1$, so they cannot be disjoint. They do not contain each
other exactly when the corresponding arrows are not nested. Note that a
pair of forward arrows such that the head of one arrow is the same as
the tail of the other is particular example of a pair of nonnested arrows.

Assume finally that one of the arrows, say $(\pi(v_{1}-1),\pi(u_{1}))$,
is a backward arrow and the other one, say $(\pi(v_{2}-1),\pi(u_{2}))$,
is a forward arrow. The image $\pi([u_{2},v_{2}-1])$
cannot be a
subset of $\pi([u_{1},v_{1}-1])$ as the first image contains
the point $n+1$ whereas the second does not.
The image $\pi([u_{1},v_{1}-1])$
is the interval $[\pi(u_{1}),\pi(v_{1}-1)]$,
whereas
the image $\pi([u_{2},v_{2}-1])$
is the union $(0,\pi(v_{2}-1)] \cup [\pi(u_{2}),n+1]$. 
The intersection of these two sets has either
zero, one or two connected components.
If one component is a single point
then this point is the head of one arrow
and the tail of the other.
If both components are non-trivial
intervals then the backward
arrow nests the forward arrow.
If they intersect in one interval
but the image $\pi([u_{1},v_{1}-1])$
does not contain
the image $\pi([u_{2},v_{2}-1])$
then the two arrows cross.
Finally, if the image $\pi([u_{1},v_{1}-1])$
does contain
the image $\pi([u_{2},v_{2}-1])$
then the arrows neither cross nor nest.
\end{proof}}  
\vanish{An immediate consequence of
\cref{proposition_across}
and \cref{lemma_facets}
is the following corollary.}
\begin{corollary}
Noncrossing sets of $B$-diagonals are represented by subsets of vertices
contained in a facet of the Legendre polytope $P_{n}$. 
\end{corollary}  



\section{The type $B$ associahedron represented
as a pulling triangulation}
\label{section_triangulation}

\vanish{In this section we show that the arc representation given in
\cref{definition_arrow_representation}
constitutes
Simion's type~$B$ associahedron $\Gamma_{n}^{B}$
as a pulling triangulation of the boundary of the Legendre polytope $P_{n}$.
Our main result is the following.}
\begin{theorem}
\label{theorem_r_pull}
Let $<$ be any linear order on the vertex set of $P_{n}$ subject to the
following conditions:
\begin{enumerate}
\itemsep=-5pt  
\item $(x_{1},y_{1})<(x_{2},y_{2})$
whenever $x_{1}-y_{1} > 0 > x_{2}-y_{2}$.
\item On the subset of vertices $(x,y)$ satisfying $x<y$, we have 
$(x_{1},y_{1})<(x_{2},y_{2})$  whenever the interval $[x_{1},y_{1}]=\{x_{1},
  x_{1}+1,\ldots, y_{1}\}$ is contained in the interval $[x_{2},y_{2}]$.
\item On the subset of vertices $(x,y)$ satisfying $x>y$, we have 
$(x_{1},y_{1})<(x_{2},y_{2})$  whenever the interval $[y_{1},x_{1}]$ is contained in
  the interval $[y_{2},x_{2}]$. 
\end{enumerate}
Then the arc representation of $\Gamma_{n}^{B}$ given in
\cref{definition_arrow_representation} is a pulling triangulation of the boundary
of the Legendre polytope $P_{n}$ with respect to $<$.
\end{theorem}
The main idea of the proof is the following. 
Recall that $\Gamma_{n}^{B}$ is a flag complex and its
minimal nonfaces are the pairs of crossing $B$-diagonals.
By \cref{theorem_pull_flag} the pulling triangulation we
defined is also a flag complex. It suffices to show that the minimal
nonfaces are in bijection. Equivalently,  
for any pair of arrows $\{(x_{1},y_{1}),(x_{2},y_{2})\}$ that form an edge in
the pulling triangulation of $P_{n}$,
these arrows correspond to a pair of noncrossing
$B$-diagonals in~$\Gamma_{n}^{B}$.
By \cref{proposition_across} this amounts to showing the
following: backward arrows cannot cross, forward arrows must nest, and
for a pair of arrows of opposite direction the backward arrow cannot
cross or nest the forward arrow. The rest of the proof is an easy
verification of these statements for the six possible relative positions
of a pair of arrows with distinct endpoints.


\vanish{\begin{proof}
Fix any pulling order $<$ satisfying the above conditions.
The first condition requires all backward arrows to precede all
forward arrows.
The next two conditions require that for a pair
of nested arrows of the same direction the nested arrow should precede
the nesting arrow.
\newcommand{\lift}[1]{\raisebox{2.5mm}{#1}}
\newcommand{\TheTable}{
\begin{table}[t]
\begin{tabular}{|c||c|c|c|}  
\hline
  Order of nodes & Arrow first pulled & Edge & Not an edge\\
\hline
\hline  
\lift{$x_{1}<x_{2}<y_{1}<y_{2}$} & \lift{$(x_{2},y_{1})$} &
\begin{dependency}[theme=simple]
\begin{deptext} $x_{1}$\& $x_{2}$ \& $y_{1}$ \& $y_{2}$\\\end{deptext}
  \depedge[arc angle=30]{1}{4}{}
  \depedge[arc angle=30]{2}{3}{}
\end{dependency}
&
\begin{dependency}[theme=simple]
\begin{deptext} $x_{1}$\& $x_{2}$ \& $y_{1}$ \& $y_{2}$\\\end{deptext}
  \depedge[arc angle=30]{1}{3}{}
  \depedge[arc angle=30]{2}{4}{}
\end{dependency}
\\
\hline
\lift{$x_{1}<y_{1}<x_{2}<y_{2}$} & \lift{$(x_{2},y_{1})$} &
\begin{dependency}[theme=simple]
\begin{deptext} $x_{1}$\& $y_{1}$ \& $x_{2}$ \& $y_{2}$\\\end{deptext}
  \depedge[arc angle=30]{1}{4}{}
  \depedge[arc angle=30]{3}{2}{}
\end{dependency}
&
\begin{dependency}[theme=simple]
\begin{deptext} $x_{1}$\& $y_{1}$ \& $x_{2}$ \& $y_{2}$\\\end{deptext}
  \depedge[arc angle=30]{1}{2}{}
  \depedge[arc angle=30]{3}{4}{}
\end{dependency}
\\
\hline
\lift{$x_{1}<y_{1}<y_{2}<x_{2}$} & \lift{$(x_{2},y_{2})$} &
\begin{dependency}[theme=simple]
\begin{deptext} $x_{1}$\& $y_{1}$ \& $y_{2}$ \& $x_{2}$\\\end{deptext}
  \depedge[arc angle=30]{1}{2}{}
  \depedge[arc angle=30]{4}{3}{}
\end{dependency}
&
\begin{dependency}[theme=simple]
\begin{deptext} $x_{1}$\& $y_{1}$ \& $y_{2}$ \& $x_{2}$\\\end{deptext}
  \depedge[arc angle=30]{1}{3}{}
  \depedge[arc angle=30]{4}{2}{}
\end{dependency}
\\
\hline
\lift{$y_{1}<x_{1}<x_{2}<y_{2}$} & \lift{$(x_{1},y_{1})$} &
\begin{dependency}[theme=simple]
\begin{deptext} $y_{1}$\& $x_{1}$ \& $x_{2}$ \& $y_{2}$\\\end{deptext}
  \depedge[arc angle=30]{2}{1}{}
  \depedge[arc angle=30]{3}{4}{}
\end{dependency}
&
\begin{dependency}[theme=simple]
\begin{deptext} $y_{1}$\& $x_{1}$ \& $x_{2}$ \& $y_{2}$\\\end{deptext}
  \depedge[arc angle=30]{2}{4}{}
  \depedge[arc angle=30]{3}{1}{}
\end{dependency}
\\
\hline
\lift{$y_{1}<x_{1}<y_{2}<x_{2}$} & \lift{$(x_{1},y_{1})$ or $(x_{2},y_{2})$}&
\begin{dependency}[theme=simple]
\begin{deptext} $y_{1}$\& $x_{1}$ \& $y_{2}$ \& $x_{2}$\\\end{deptext}
  \depedge[arc angle=30]{2}{1}{}
  \depedge[arc angle=30]{4}{3}{}
\end{dependency}
&
\begin{dependency}[theme=simple]
\begin{deptext} $y_{1}$\& $x_{1}$ \& $y_{2}$ \& $x_{2}$\\\end{deptext}
  \depedge[arc angle=30]{2}{3}{}
  \depedge[arc angle=30]{4}{1}{}
\end{dependency}
\\
\hline
\lift{$y_{1}<y_{2}<x_{1}<x_{2}$} & \lift{$(x_{1},y_{2})$} &
\begin{dependency}[theme=simple]
\begin{deptext} $y_{1}$\& $y_{2}$ \& $x_{1}$ \& $x_{2}$\\\end{deptext}
  \depedge[arc angle=30]{3}{2}{}
  \depedge[arc angle=30]{4}{1}{}
\end{dependency}
&
\begin{dependency}[theme=simple]
\begin{deptext} $y_{1}$\& $y_{2}$ \& $x_{1}$ \& $x_{2}$\\\end{deptext}
  \depedge[arc angle=30]{3}{1}{}
  \depedge[arc angle=30]{4}{2}{}
\end{dependency}
\\
\hline
\end{tabular}
\vspace*{3mm}
\caption{Pairs of arrows that are edges or minimal nonfaces}
\label{table_six_way}  
\end{table}
}

\TheTable


Recall that~$\Gamma_{n}^{B}$ is a flag complex and its
minimal nonfaces are the pairs of crossing $B$-diagonals.
By \cref{theorem_pull_flag} the pulling triangulation we
defined is also a flag complex. It suffices to show that the minimal
nonfaces are in bijection. Equivalently,  
for any pair of arrows $\{(x_{1},y_{1}),(x_{2},y_{2})\}$ that form an edge in
the pulling triangulation of $P_{n}$,
these arrows correspond to a pair of noncrossing
$B$-diagonals in~$\Gamma_{n}^{B}$.
By \cref{proposition_across} this amounts to showing the
following: backward arrows cannot cross, forward arrows must nest, and
for a pair of arrows of opposite direction the backward arrow cannot
cross or nest the forward arrow.




Given a four-element subset $\{x_{1},x_{2},y_{1},y_{2}\}$
of $\{1, 2, \ldots, n+1\}$,
where $x_{1} < x_{2}$ and $y_{1} < y_{2}$,
consider the four arrows
in the set $\{x_{1},x_{2}\} \times \{y_{1},y_{2}\}$.
As seen in
\cref{lemma_square}, these four arrows form the vertex set of a
square face of the Legendre polytope $P_{n}$, and only the diagonal
which contains the first vertex to be pulled is an edge of the pulling
triangulation.
\cref{table_six_way}
lists all six possible orderings of this four element set.

In each of the six cases we note which vertex is pulled first,
which diagonal of the square becomes an edge in the 
triangulation and which diagonal does not become an edge.
Note that in the fifth row
of \cref{table_six_way}
we have two possibilities for selecting the vertex to be pulled first.
However, these two vertices belong to the same diagonal.
In every case
we obtain that none of the pairs of arrows with distinct heads and tails
that is an edge corresponds to a pair of crossing
$B$-diagonals. 
\end{proof}}


As a corollary we obtain Simion's polytopal result.
\begin{corollary}[Simion]
The Simion type $B$ associahedron $\Gamma_{n}^{B}$ is
the boundary complex of a simplicial polytope.
\end{corollary}
Since the associahedron of type $A$
is the link of a $B$-diagonal
of the form~$\{i,\overline{i}\}$, we obtain the following classical result;
see the work of Haiman, Lee~\cite{Lee} and Stasheff.
For a brief history, see the introduction
of~\cite{Ceballos_Santos_Ziegler}.
\begin{corollary}
The associahedron is
the boundary complex of a simplicial polytope.
\end{corollary}


We end this section by describing
the structure of all facets
of the Simion's type $B$ associahedron
in terms of arrows.
\begin{theorem}
\label{theorem_arrow}
A set of arrows $S=\{(x_{1},y_{1}),\ldots,(x_{n},y_{n})\}$ represents a facet of
Simion's type~$B$ associahedron $\Gamma_{n}^{B}$
if and only if the following conditions are satisfied: 
\begin{enumerate}
\itemsep=-5pt
\item There is exactly one integer $k$ satisfying $1 \leq k \leq n+1$
such that $(k-1,k)$
(or $(n+1,1)$ if $k=1$) belongs the set~$S$. We call this $k$ the {\em
type} of the facet. 
\item Backward arrows do not nest any forward arrow, in particular, they
cannot nest $(k-1,k)$ if $k>1$. 
\item If $k=1$ then there is no forward arrow in the set $S$.
\item Forward arrows must nest. In particular, if $k>1$ then for each
each forward arrow $(x,y)\in S$ must satisfy $x\leq k-1$
and $y \geq k$. (Forward arrows must nest $(k-1,k)$.) 
\item
No head of an arrow in the set $S$
is also the tail of another arrow in $S$.
\item No two arrows cross.
\end{enumerate} 
\end{theorem}
\vanish{\begin{proof}
Condition~(1) is equivalent to
\cref{lemma_diameter}.
Except for Condition~(3), the remaining conditions are stated for all
faces in \cref{proposition_across}. To prove Condition~(3), observe
that $k=1$ implies that the backward arrow $(n+1,1)$ belongs to
$S$. This arrow would nest any forward arrow, contradicting
Condition~(3) in \cref{proposition_across}. 
\end{proof}}


\section{Triangulating Cho's decomposition}
\label{section_Cho}

The type $A$ root polytope $P_{n}^{+}$
is the convex hull of the origin and the set of points
$\{e_{i} - e_{j} \: :\: 1 \leq i < j \leq n+1\}$.
Cho~\cite{Cho} gave a decomposition
of the Legendre polytope~$P_{n}$
into $n+1$ copies of $P_{n}^{+}$ as follows. The symmetric group
$\SSSS_{n+1}$ acts on the Euclidean space $\Rrr^{n+1}$ by
permuting the coordinates, that is, the permutation
$\sigma \in \SSSS_{n+1}$ sends the
basis vector $e_{i}$ into $e_{\sigma(i)}$. Hence the permutation~$\sigma$
acts on the Legendre polytope $P_{n}$ by sending each $e_{i}-e_{j}$ into
$e_{\sigma(i)}-e_{\sigma(j)}$.
Cho's main result~\cite[Theorem~16]{Cho} is
the following decomposition.
\begin{theorem}[Cho]
The Legendre polytope $P_{n}$ has the decomposition 
$$ P_{n}  =  \bigcup_{k=0}^{n} \zeta^{k}(P_{n}^{+}) $$ 
where $\zeta$ is the cycle $(1,2,\ldots,n+1)$.
Furthermore, for $0 \leq k < r \leq n$
the polytopes $\zeta^{k}(P_{n}^{+})$ and $\zeta^{r}(P_{n}^{+})$
have disjoint interiors.
\label{theorem_Cho}
\end{theorem}
The following theorem implies that each copy $\zeta^{k}(P_{n}^{+})$ of
$P_{n}^{+}$ is the union of simplices of the triangulation given in
\cref{definition_arrow_representation}, representing the
boundary complex $\Gamma_{n}^{B}$ of Simion's type $B$ associahedron.  

\begin{theorem}
Every facet $F$ of the arc representation of $\Gamma_{n}^{B}$ given in
\cref{definition_arrow_representation} is contained in
$\zeta^{k-1}(P_{n}^{+})$ 
where $k$ is the unique arrow of the form $(k-1,k)$ in $F$
or $(n+1,1)$ if $k=1$.
Equivalently, the facet $F$ is contained in $\zeta^{k}(P_{n}^{+})$
exactly when it represents a facet of $\Gamma_{n}^{B}$
that contains the diagonal~$\{k,\overline{k}\}$.
\end{theorem}  
\vanish{\begin{proof}
The polytope $P_{n}^{+}$ is the convex hull the origin and of all vertices that are
represented by backward arrows. The facets of type $1$ (as defined in
\cref{theorem_arrow}) form a pulling triangulation of the part of the
boundary of $P_{n}^{+}$ that does not contain the origin. In fact, the
restriction of the pulling order to the backward arrows may be taken in the
{\em revlex order}, as defined in \cite[Definition~4.5]{Hetyei-Legendre}, giving
rise to the {\em standard triangulation} described
in~\cite{Gelfand-Graev-Postnikov}. A facet in our triangulation of $P_{n}$
belongs to the standard triangulation of the boundary of the part of
$P_{n}^{+}$ not containing the origin exactly when it has type $1$.

Observe next that the effect of $\zeta$ on the arrows (considered as
vertices of $P_{n}$) is adding $1$ modulo $n+1$ to the head and to the
tail of each arrow. Taking into account
\cref{definition_arrow_representation}
and
\cref{remark_arrows}, it is not difficult to see that the induced effect
on the arc representation is adding $1$ modulo $n+1$, that is, a
rotation. It is worth noting that to rotate each vertex of a regular
$(2n+2)$-gon into itself requires increasing each index by one $2n+2$
times. However, a centrally symmetric pair of arcs $\{[u, v-1], [u+n+1,
  v+n]\}$ is taken into itself already by $n+1$ such elementary
rotations. In the arc representation the facets containing only backward
arrows corresponding to facets containing the pair of arcs
$\{[1,n+1],[n+2,2n+2]\}$. The induced action of $\zeta^{k-1}$ takes this
pair into $\{[k,n+k],[n+k+1,2n+1+k]\}$. The conditions stated in
\cref{theorem_across} are rotation-invariant, so the induced action
of $\zeta^{k-1}$ takes the family of all facets containing
$\{[1,n+1],[n+2,2n+2]\}$ into the family of all facets containing 
$\{[k,n+k],[n+k+1,2n+1+k]\}$.
\end{proof}}




\section{Concluding Remarks}

For complete proofs, we refer the reader to the full length 
version of this extended abstract~\cite{Ehrenborg-Hetyei-Readdy}.


Simion observed algebraically that the number of $k$-dimensional
faces of the type~$B$ associahedron is given by the number of {\em balanced
  Delannoy paths} between $(0,0)$ and $(2n,0)$ taking 
$k$ up steps $(1,1)$, $k$ down steps $(1,-1)$, and $n-k$ horizontal
steps $(2,0)$. We have found a combinatorial proof by providing
a non-recursive bijection between the faces of the type~$B$ associahedron
and Delannoy paths~\cite[Section~8]{Ehrenborg-Hetyei-Readdy}.

In a recent paper, Cellini and Marietti~\cite{Cellini_Marietti_abelian} used
abelian ideals to produce a triangulation for various root polytopes.
In the case of type $A$, their
construction yields once again a lexicographic triangulation of
each face.  Restricting to the positive roots yields Gelfand, Graev
and Postnikov's anti-standard tree bases for the type $A$ positive
root polytope.  Is there an ideal corresponding to the reverse
lexicographic triangulation?



The $h$-vector of Simion's type~$B$ associahedron
may be computed from the $f$-vector using
elementary operations on binomial coefficients;
see~\cite[Corollary 1]{Simion}. 
\begin{lemma}[Simion]
The $h$-vector $(h_{0}, h_{1}, \ldots, h_{n})$ of
Simion's type~$B$ associahedron~$\Gamma_{n}^{B}$ satisfies 
$$
h_{i}=\binom{n}{i}^{2}\quad \mbox{for $0\leq i\leq n$}.
$$
\end{lemma}    
\noindent
One of the referees
pointed out the recent work of Ceballos, Padrol and
Sarmiento, in which 
they recover our pulling triangulation of the bounday of the Legendre
polytope~\cite[Theorem  8.5]{Ceballos-Padrol-Sarmiento}. 
Much earlier Billera, Cushman and Sanders describe
an explicit shelling using lattice paths
and recover the values $h_i$ as counting those lattice
paths having~$i$ corners~\cite[Section 3]{Billera_Cushman_Sanders}.
The fact that the number of such lattice paths
is given by 
$\binom{n}{i}^{2}$ is a classical result
of MacMahon from 1915~\cite[Vol.\ I, Article~89, pp.~119-120]{MacMahon}.


Finally, are there other interesting simplicial polytopes that
can be better understood as pulling triangulations of less
complicated polytopes?



\acknowledgements{The first author was partially funded by
the National Security Agency grant H98230-13-1-028.
This work was partially supported by two grants from the
Simons Foundation
(\#245153 to G\'abor Hetyei and \#206001 to Margaret Readdy).
The authors thank the Princeton University Mathematics Department
where this research was initiated, and two anonymous referees for many
insightful comments.}

\printbibliography


\end{document}
